package com.dy.串;

import java.util.Arrays;

public class SeqString implements IString {


    private char[] strvalue;
    private int curlen;

    public SeqString() {
        strvalue = new char[0];
        curlen = 0;
    }

    public SeqString(String str) {
        char[] temp = str.toCharArray();
        strvalue = temp;
        curlen = str.length();
    }

    public SeqString(char[] value) {
        char[] tmp = new char[value.length];
        for (int i = 0; i < value.length; i++) {
            tmp[i] = value[i];
        }
        curlen = value.length;
    }


    @Override
    public void clear() {
        this.curlen = 0;
    }

    @Override
    public boolean isEmpty() {
        return curlen == 0;
    }

    @Override
    public int length() {
        return curlen;
    }

    @Override
    public char charAt(int index) {
        if (index < 0 || index >= curlen) {
            throw new StringIndexOutOfBoundsException(index);
        } else return strvalue[index];
    }

    //字符串扩容
    public void allocate(int newCapacity) {
        char[] temp = strvalue;
        strvalue = new char[newCapacity];
        for (int i = 0; i < temp.length; i++) {
            strvalue[i] = temp[i];
        }

    }

    @Override
    public IString substring(int begin, int end) {
        char[] tmp = new char[end - begin];
        for (int i = 0; i < tmp.length; i++) {
            tmp[i] = strvalue[i + begin];
        }
        return new SeqString(tmp);
    }

    @Override
    public IString insert(int offset, IString str) {
        int len = str.length();
        int newCount = len + this.curlen;
        if (newCount > strvalue.length) {
            allocate(newCount);
        }
        for (int i = this.curlen - 1; i >= offset; i--) {
            strvalue[i + len] = strvalue[i];
        }
        for (int i = 0; i < len; i++) {
            strvalue[i + offset] = str.charAt(i);
        }
        this.curlen = newCount;
        return this;
    }

    @Override
    public IString delete(int begin, int end) {
        for (int i = begin; i < curlen - end; i++) {
            strvalue[i] = strvalue[end + i];
        }
        curlen = curlen - (end - begin);
        return this;
    }

    //连接
    @Override
    public IString concat(IString str) {
        return insert(curlen, str);
    }

    @Override
    public int compareTo(IString str) {
        int len1 = curlen;
        int len2 = str.length();
        int n = Math.min(len1, len2);
        for (int i = 0; i < n; i++) {
            if (str.charAt(i) != this.charAt(i)) {
                return this.charAt(i) - str.charAt(i);
            }
        }
        return len1 - len2;
    }
    //暴力和kmp

    //brute force
    @Override
    public int indexOf(IString str, int begin) {
        int slen = this.length();
        int tlen = str.length();
        int i = begin, j = 0;
        while (i < slen && j < tlen) {
            if (strvalue[i] == str.charAt(j)) {
                i++;
                j++;
            } else {
                i = i - j + 1;
                j = 0;
            }

        }
        if (j == tlen) {
            return i - tlen;
        } else return -1;
    }

    //KMP

    /**
     * 计算next数组
     * 前缀后缀
     * 如：
     * abcabc 前缀有 a ab abc abca abcab 后缀有 c bc abc cabc bcabc
     * next数组第一个是-1，第二个是0，之后标号是i，数字是 0~i-1的字符串前后缀相同的个数
     * next[j] = k 代表p[j] 之前的模式串子串中，有长度为k 的相同前缀和后缀。
     * <p>
     * d   a   a   c   d   a   a    d    e
     * -1  0   0   0   0   1   2    3    1
     * <p>
     * next数组在匹配时，失配的情况下，j变到next[j],i不回退
     */
    public static void main(String[] args) {
        SeqString sq = new SeqString("ababcabdabcabca");
        SeqString sq2 = new SeqString("abcabc");
        //System.out.println(sq.indexOf(sq2, 0));
        Arrays.stream(getNextVal("abab")).forEach(System.out::println);
        System.out.println(kmp("ababcabdabcabca", "abab"));
    }

    public static int[] getNext(String ps) {

        char[] p = ps.toCharArray();
        int[] next = new int[p.length];
        next[0] = -1;
        int j = 0;
        int k = -1;
        while (j < p.length - 1) {
            if (k == -1 || p[j] == p[k]) {
                next[++j] = ++k;
            } else {
                k = next[k];
            }
        }
        return next;

    }


    public static int[] getNextVal(String ps) {

        char[] p = ps.toCharArray();

        int[] next = new int[p.length];

        next[0] = -1;

        int j = 0;

        int k = -1;

        while (j < p.length - 1) {

            if (k == -1 || p[j] == p[k]) {

                if (p[++j] == p[++k]) { // 当两个字符相等时要跳过

                    next[j] = next[k];

                } else {

                    next[j] = k;

                }

            } else {

                k = next[k];

            }

        }

        return next;

    }


    public static int kmp(String s, String t) {
        int[] next = getNext(t);
        int i, j;
        for (i = 0, j = 0; i < s.length() && j < t.length(); ) {
            if (j == -1 || s.charAt(i) == t.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if (j < t.length()) {
            return -1;
        } else {
            return i - t.length();
        }
    }
}
